1. Field of the Invention
The present invention relates to a Huffman decoding method, and more particularly, to a Huffman decoding method which has a higher searching speed and less memory usage than conventional methods.
2. Description of the Prior Art
Huffman coding is a highly popular compression technique that is used in many standards, including MPEG AAC (Moving Picture Experts Group Advanced Audio Coding) and JPEG (joint Photographic Experts Group). It greatly compresses a stream size of audio or video media. However, Huffman coding also provides a computational burden for an encoder and especially for a decoder because Huffman decoding is one of the most computationally intensive modules in audio or video decoders. In addition, many embedded systems are dedicated decoders but have limited resources and clock rate. Therefore, these embedded systems must process the Huffman code efficiently while utilizing limited resources, such as limited memory space.
Different kinds of Huffman decoding methods have been proposed previously, and these existing decoding techniques can be divided into two categories: single bit methods and multiple bit methods. Both travel on the Huffman tree method and the method described in the JPEG standard use the single bit decoding technique. Multiple bit methods usually employ table lookup or searching techniques to find Huffman codes instead of searching codes bit by bit.
The single bit methods are very slow because the Huffman decoding results are searched bit by bit. Nowadays, audio streams or JPEG images handled in embedded systems have high bit rate or resolutions. Efficient processing of these audio streams and images is very important because most embedded systems have low clock rate to reduce system power consumption. Therefore, the single bit methods are not suitable for most embedded systems because they are inefficient in decoding Huffman codes.
The multiple bit methods were invented to speed up the Huffman decoding. Most multiple bit methods, especially table lookup approaches, decode data much faster than the single bit methods. However, the multiple bit methods use much more memory space, and therefore are not perfect for the embedded systems because most embedded systems have limited memory space in order to reduce cost and chip size.